package tree

import "fmt"

type TreeNode struct {
	Val        int
	LeftChild  *TreeNode
	RightChild *TreeNode
}

func PreOrderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	preOrderTraversalHelper(root, &result)
	fmt.Println(result)
	return result
}

func preOrderTraversalHelper(root *TreeNode, resultList *[]int) {
	if root == nil {
		return
	}
	*resultList = append(*resultList, root.Val)
	preOrderTraversalHelper(root.LeftChild, resultList)
	preOrderTraversalHelper(root.RightChild, resultList)
}

func InOrderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	inOrderTraversalHelper(root, &result)
	fmt.Println(result)
	return result
}

func inOrderTraversalHelper(root *TreeNode, resultList *[]int) {
	if root == nil {
		return
	}
	inOrderTraversalHelper(root.LeftChild, resultList)
	*resultList = append(*resultList, root.Val)
	inOrderTraversalHelper(root.RightChild, resultList)
}

func PostOrderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	postOrderTraversalHelper(root, &result)
	fmt.Println(result)
	return result
}

func postOrderTraversalHelper(root *TreeNode, resultList *[]int) {
	if root == nil {
		return
	}
	postOrderTraversalHelper(root.LeftChild, resultList)
	postOrderTraversalHelper(root.RightChild, resultList)
	*resultList = append(*resultList, root.Val)
}

//通过数组构建完全二叉树(这样不一定能构造出完全二叉树)，不过AVL树是可如此构建的
func CompleteBinarySeachTree(input []int) *AVLNode {
	if len(input) == 0 {
		return nil
	}
	if len(input) == 1 {
		return &AVLNode{
			V: input[0],
		}
	}
	rootIndex := len(input) / 2
	resNode := &AVLNode{
		V: input[rootIndex],
		L: CompleteBinarySeachTree(input[:rootIndex]),
		R: CompleteBinarySeachTree(input[rootIndex+1:]),
	}
	resNode.updateHeight()
	return resNode
}
